After the work of Impagliazzo and Rudich (STOC, 1989), the black box framework has become one of the main research domain of cryptography. However black box techniques say nothing about non-black box techniques such as making use of zero-knowledge proofs. Brakerski et al. introduced a new black box framework named augmented black box framework, in which they gave a zero-knowledge proof oracle in addition to a base primitive oracle (TCC, 2011). They showed a construction of a non-interactive zero knowledge proof system based on a witness indistinguishable proof system oracle. They presented augmented black box construction of chosen ciphertext secure public key encryption scheme based on chosen plaintext secure public key encryption scheme and augmented black box separation between one-way function and key agreement. In this paper we simplify the work of Brakerski et al. by introducing a proof system oracle without witness indistinguishability, named coin-free proof system oracle, that aims to give the same construction and separation results of previous work. As a result, the augmented black box framework becomes easier to handle. Since our oracle is not witness indistinguishable, our result encompasses the result of previous work.

Bilinear-type conversion is to translate a cryptographic scheme designed over symmetric bilinear groups into one that works over asymmetric bilinear groups with small overhead regarding the size of objects concerned in the target scheme. In this paper, we address scalability for converting complex cryptographic schemes. Our contribution is threefold. Investigating complexity of bilinear-type conversion. We show that there exists no polynomial-time algorithm for worst-case inputs under standard complexity assumption. It means that bilinear-type conversion in general is an inherently difficult problem. Presenting a new scalable conversion method. Nevertheless, we show that large-scale conversion is indeed possible in practice when the target schemes are built from smaller building blocks with some structure. We present a novel conversion method, called IPConv, that uses 0-1 Integer Programming instantiated with a widely available IP solver. It instantly converts schemes containing more than a thousand of variables and hundreds of pairings. Application to computer-aided design. Our conversion method is also useful in modular design of middle to large scale cryptographic applications; first construct over simpler symmetric bilinear groups and run over efficient asymmetric groups. Thus one can avoid complication of manually allocating variables over asymmetric bilinear groups. We demonstrate its usefulness by somewhat counter-intuitive examples where converted DLIN-based Groth-Sahai proofs are more compact than manually built SXDH-based proofs. Though the early purpose of bilinear-type conversion is to save existing schemes from attacks against symmetric bilinear groups, our new scalable conversion method will find more applications beyond the original goal. Indeed, the above computer-aided design can be seen as a step toward automated modular design of cryptographic schemes.

This paper presents a Mix-net that has the following properties; (1) it efficiently handles long plaintexts that exceed the modulus size of the underlying public-key encryption scheme as well as very short ones (length-flexibility), (2) input ciphertext length is not impacted by the number of mix-servers (length-invariance), and (3) its security in terms of anonymity can be proven in a formal way (probable security). If desired, one can add robustness so that it outputs correct results in the presence of corrupt users and servers. The security is proven in such a sense that breaking the anonymity of our Mix-net is equivalent to breaking the indistinguishability assumption of the underlying symmetric encryption scheme or the Decision Diffie-Hellman assumption.

We present an efficient Hybrid Mix scheme that provides both routing flexibility and the optimal length of ciphertext. Although it is rather easy to embed routing information in the ciphertext, and a scheme that provides the optimal length of ciphertext is already known, it is not a trivial task to achieve both properties all at the same time. A critical obstacle for providing the optimal length of ciphertext is the session-key encapsulation header in a ciphertext that carries the encrypted session-key to each router, which linearly increases according to the number of intermediate routers. We solve this problem by improving the previously reported Hybrid Mix scheme such that the resulting scheme benefits from routing flexibility with a constant length of such headers. Our basic scheme is only secure against honest, but curious intermediate routers. Therefore, we further address the robustness issue to prevent malicious behavior by incorporating and improving an existing efficient approach based on the Message Authentication Code.

This paper addresses how to use public-keys of several different signature schemes to generate 1-out-of-n signatures. Previously known constructions are for either RSA-type keys only or DL-type keys only. We present a widely applicable method to construct a 1-out-of-n signature scheme that allows mixture use of different flavors of keys at the same time. The resulting scheme is more efficient than previous schemes even if it is used only with a single type of keys. With all DL-type keys, it yields shorter signatures than the ones of the previously known scheme based on the witness indistinguishable proofs by Cramer, et al. With all RSA-type keys, it reduces both computational and storage costs compared to that of the Ring signatures by Rivest, et al.

This paper studies the relations among several definitions of anonymity for ring signature schemes in the same attack environment. It is shown that one intuitive and two technical definitions we consider are asymptotically equivalent, and the indistinguishability-based technical definition is the strongest, i.e., the most secure when achieved, when the exact reduction cost is taken into account. We then extend our result to the threshold case where a subset of members cooperate to create a signature. The threshold setting makes the notion of anonymity more complex and yields a greater variety of definitions. We explore several notions and observe certain relation does not seem hold unlike the simple single-signer case. Nevertheless, we see that an indistinguishability-based definition is the most favorable in the threshold case. We also study the notion of linkability and present a simple scheme that achieves both anonymity and linkability.

We construct the first fully homomorphic encryption (FHE) scheme that encrypts matrices and supports homomorphic matrix addition and multiplication. This is a natural extension of packed FHE and thus supports more complicated homomorphic operations. We optimize the bootstrapping procedure of Alperin-Sheriff and Peikert (CRYPTO 2014) by applying our scheme. Our optimization decreases the lattice approximation factor from Õ(n3) to Õ(n2.5). By taking a lattice dimension as a larger polynomial in a security parameter, we can also obtain the same approximation factor as the best known one of standard lattice-based public-key encryption without successive dimension-modulus reduction, which was essential for achieving the best factor in prior works on bootstrapping of standard lattice-based FHE.